package com.lfg.leetcode.leetcode0;


public class No33Search {


    public static int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int maxIndex = getMaxIndex(nums);
        int i = 0;
        int j = 0;
        int endIndex = nums.length - 1;
        if (maxIndex == endIndex) {
            j = endIndex;
        } else if (nums[0] <= target) {
            i = 0;
            j = maxIndex;
        } else if (nums[maxIndex + 1] <= target) {
            i = maxIndex + 1;
            j = endIndex;
        } else {
            return -1;
        }

        while (i <= j) {
            int middle = (i + j) / 2;
            if (target < nums[middle]) {
                j = middle - 1;
            } else if (target > nums[middle]) {
                i = middle + 1;
            } else if (target == nums[middle]) {
                return middle;
            } else {
                return -1;
            }
        }
        return -1;
    }

    private static int getMaxIndex(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        if (nums[j] >= nums[i]) {
            return j;
        }

        while (i <= j) {
            int middle = (i + j) / 2;
            if (nums[i] > nums[middle]) {
                j = middle - 1;
            } else if (nums[middle] > nums[j]) {
                i = middle;
                j--;
            } else {
                return j;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        int ret = search(new int[]{9,10,11,0,1,2, 3,4,5,6,7,8},1);
        int ret = search(new int[]{3, 1}, 0);
        System.out.println(ret);
    }
}

